#include "heap.h"

void heapinit(heap* php)
{
	assert(php);
	/*hp->a = (hpdatatype*)malloc(sizeof(hpdatatype));
	if (hp->a == NULL)
	{
		exit(-1);
	}*/
	php->a = NULL;
	php->size = 0;
	php->capicity = 0;
}

void heappush(heap* php, hpdatatype x)
{
	assert(php);
	int newcapicity = 0;
	if (php->capicity == php->size)
	{
		newcapicity = php->capicity == 0 ? 4 : 2 * php->capicity;
		hpdatatype* tmp = (hpdatatype*)realloc(php->a,sizeof(hpdatatype) * newcapicity);
		if (tmp == NULL)
		{
			exit(-1);
		}
		php->capicity = newcapicity;
		php->a = tmp;
	}
	php->a[php->size] = x;
	php->size++;
	adjustup(php->a, php->size-1);
}

void adjustup(hpdatatype* p, int child)
{
	assert(p);
	int parent = 0;
	parent = (child - 1) / 2;
	while (child>0)
	{
		if (p[parent] < p[child])
		{
			swap(&p[parent], &p[child]);
		}
		else
		{
			break;
		}
		child = parent;
		parent = (child - 1) / 2;

	}
	
}

void swap(hpdatatype* p, hpdatatype* c)
{
	assert(p);
	assert(c);
	hpdatatype tmp=0;
	tmp = *p;
	*p = *c;
	*c = tmp;
}

void heapprint(heap* php)
{
	assert(php);
	assert(!heapempty(php));
	int i = 0;
	for(i=0;i<php->size;i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

void heappop(heap* php)
{
	assert(php);
	assert(!heapempty(php));
	if (php->size > 0)
	{
		swap(&(php->a[0]), &(php->a[php->size-1]));
		php->size--;
		adjustdown(php->a, php->size);
	}
}

void adjustdown(hpdatatype* p, int si)
{
	int parent = 0;
	int bigchild = 2*parent+1;
	while (bigchild<si)
	{
		if ((p[bigchild] < p[bigchild + 1])&&(bigchild+1)<si)
		{
			bigchild = bigchild + 1;
		}
		if (p[parent] < p[bigchild])
		{
			swap(&p[parent], &p[bigchild]);
		}
		else
		{
			break;
		}
		parent = bigchild;
		bigchild = 2 * parent+1;
	}

}

bool heapempty(heap* php)
{
	assert(php);
	if (php->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}


hpdatatype heaptop(heap* php)
{
	assert(php);
	assert(!heapempty(php));
	return (php->a[0]);
}

int heapsize(heap* php)
{
	assert(php);
	assert(!heapempty(php));
	return (php->size);
}

void heapdestory(heap* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
}

void heapsort(heap* php, hpdatatype* a,int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		heappush(php, a[i]);
	}
	while (sz)
	{
		swap(&(php->a[0]), &(php->a[sz - 1]));
		sz--;
		adjustdown(php->a, sz);
	}
}